package com.zhengb.algorithmdemo.basic.stack;

/**
 * Created by zhengbo on 2020/2/19.
 */
public class StackSort {

    public static LinkListBaseStack<Integer> stackSort(LinkListBaseStack<Integer> stack) {

        LinkListBaseStack<Integer> r = new LinkListBaseStack<>();

        while (!stack.isEmpty()) {
            int tmp = stack.pop();
            while (!r.isEmpty() && r.pop() > tmp) {
                stack.push(r.pop());
            }
            r.push(tmp);
        }

        return r;
    }

    public static void main(String[] args) {

        LinkListBaseStack<Integer> stack = new LinkListBaseStack<>();

        stack.push(1);
        stack.push(3);
        stack.push(5);
        stack.push(4);
        stack.push(2);

        LinkListBaseStack<Integer> sortedStack = stackSort(stack);

        System.out.println(sortedStack.getStackList());

    }
}
